This invention pertains to a unique communication-network topology discovery practice which is implementable as a step in a dynamic overall process leading to self-organization of a collection of nodes into an ad hoc network. The invention is useful in organizing both distributed and centralized communication-networks. While the overall practice of ad hoc network organization involves a number of other steps and stages, the present invention focuses only on a topology discovery sub-practice within that overall practice.
Useful and related background information, which is hereby incorporated by reference into this disclosure, is found in prior-filed, co-pending U.S. Regular Patent Applications filed by me on Feb. 9, 2004 including (a) Ser. No. 10/775,717 for “Centralized Network Organization and Topology Discovery in Ad-Hoc network with Central Controller” and, (b) Ser. No. 10/775,967 for “Distributed Network Organization and Topology Discovery in Ad-Hoc Network”.
Fundamentally, and generally speaking, topology discovery involves a practice wherein all nodes which are to be assembled into a network, or are about to be linked in an otherwise pre-existing network, learn of each other's presences, and about each other's operating and linking characteristics and capabilities. More specifically, topology discovery pertains to knowledge regarding, among other things as will become apparent, (a) the identities of all nodes in a network, (b) the states of existing/possible connectivity between these nodes, (c) the identity of ultimately an eventually selected CCo (Central Coordinator Node), (d) the identities of so-called hidden nodes (defined below), and (e) the identities of what are referred to herein (later explained) as proxy nodes.
In a self-organizing ad hoc communication network, nodes need to learn about the presences of other nodes in the network, and about the availabilities of acceptable bi-directional links between any two nodes. The nodes must also be able to organize themselves into a network controlled ultimately by a suitable, selected CCo. Ultimately, and in accordance with practice of the present invention, in a resulting, completely organized network, every node will know the state of links existing between all nodes in the network. In other words, all nodes will have and maintain knowledge about the global state of connectivity in the network, including specific information relating to relevant individual characteristics of each node.
The topology discovery process of this invention, implemented via a discover beacon, is employed under different defined, or definable, dynamic and changing conditions, such as (a) during initial network organization, (b) in a situation wherein a node joins or leaves the network, (c) during recovery from network or node failure, (d) upon the occurrence of any event that changes the topology of a network, such as a circumstance wherein the CCo shuts down, or a better suited CCo becomes available in a network, and (e) other changing network conditions. The discover beacon indicates to listening nodes periods of time within a frame when they may transmit any messages required to join/associate with the network, thus to be discovered. Additionally, the discover beacon echoes frame-schedule information contained within a master beacon transmitted by a network controller, if such a controller should then exist, and if such a controller does not then exist, involves a time-frame schedule which is consistent with schedules broadcast by other nodes.
It is important to understand that “topology discovery”, as proposed by the present invention, and as used as a term herein, is a dynamic practice. It is defined to include, among other things, the ongoing background collection and assessment of internodal link-capabilities information, and appropriate list updating, derived from network transmissions, and obtained and made useable at a level enabling a CCo always to be poised to organize (and re-organize) the associated network into appropriate groupings—i.e., sub-nets and proxy networks. Such organizational behavior includes, of course, the positive “creation” of appropriate links between nodes, based upon matters including an understanding of existing and possible connectivities, and most certainly upon identified node operating capabilities. In other words, “topology discovery” is not constrained simply to the matters of communication routing between nodes.
It additionally involves the important individual nodal behavior of listening to topology discovery messages so as to obtain ongoing guidance regarding various network access opportunities.
Topology discovery, as proposed by the present invention, is described herein in two different general network configurations, referred to, on the one hand, as centralized and on the other, as distributed. As will be seen shortly, in a centralized network, the CCo, which acquires such a role in a manner shortly to be described, following the practice of topology discovery, itself creates what is referred to herein as a topology map, or table, of the associated network. In a distributed network, it is the individual participating nodes which, operating collectively after completion of the process of topology discovery, create and each hold a network topology map. From this established map, however arrived at, full network organization takes place, such activity being beyond the scope of the present invention.
Before describing the topology discovery practice of the invention, two language terms which are employed herein should be explained. These terms are “hidden node”, or HN, and “proxy node”, or PN (or PCo). A hidden node is one which cannot communicate directly with a network CCo. A proxy node is one which acts as a CCo surrogate to provide a communication path between the network CCo and a hidden node.
In further general terms, the topology-discovery method of this invention can be described as including the steps of: (a) defining an appropriate topology-discovery condition which may be associated with plural nodes that are to be organized into a network; (b) on the occurrence of the existence of such a condition, establishing and activating a discovery-communication time period which is dedicated to allowing each of the plural nodes to broadcast, for reception by all of the other nodes, its attributes, including its identity, it operating characteristics, its capabilities, and its associated link qualities in relation to the other nodes, whereby ultimately every one of the plural nodes becomes aware of these attributes of all of the other nodes; (c) utilizing the results of the establishing and activating steps, creating a topology map associated with the nodes, and (d) then making the created topology map available for use in a process involving subsequent organization of the nodes into a network.
As will be seen, the created topology map, among other things, contains a network connectivity map, and additionally, may be employed to enable information packet routing.
The various features and advantages that are offered by the present invention will become more fully apparent as the description which now follows is read in conjunction with the accompanying drawings.